// https://leetcode.cn/problems/maximum-subarray/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // if (nums.empty()) return 0;
        // int n = nums.size();
        // vector<int> rec(n, 0); //rec[i]表示以 nums[i] 结尾的连续子数组的最大和
        // rec[0] = nums[0];
        // // int maxVal = 0;
        // int maxVal = INT_MIN;
        // for (int i = 1; i < n; ++i) {
        //     if(rec[i - 1] > 0) rec[i] = rec[i - 1] + nums[i];
        //     else rec[i] = nums[i];
        // }
        // for (int i = 0; i < rec.size(); ++i) {
        //     maxVal = max(maxVal, rec[i]);
        // }
        // return maxVal;

        // dp[i] 的值只和 dp[i - 1] 有关，因此可以使用「滚动变量」的方式将代码进行优化。
        if (nums.empty()) return 0;
        int pre = 0, res = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            pre = max(pre + nums[i], nums[i]);
            res = max(pre, res);
        }
        return res;
    }
};